1. Field of the Invention
The present invention relates to a prefetching apparatus, a prefetching method, and a prefetching program. Particularly, the present invention relates to a prefetching apparatus for prefetching data from a file to a buffer before the data is read by a program, and a prefetching method and a prefetching program therefor.
2. Background of the Invention
As a consequence of recent increases in the processing speeds of processors, the times required to read data from external storage devices, such as hard disk drives, are greatly extended, when compared with the processing times of the processors. Therefore, when to process data a processor must first read the data from an external storage device, the processor will frequently fall into an input/output wait (IO wait) state during an extended period between the time a reading request is issued to the external storage device and the time the reading is completed.
As methods for preventing performance reductions due to input/output wait times, various techniques have been proposed for the prefetching (prefetching) of data stored on external storage devices.
In non-patent documents 1 and 2, techniques are disclosed whereby whether a file is read sequencially is detected each time a program is executed, and when the file is read sequencially, the file is prefetched sequencially from top of the file to the bottom.
In non-patent documents 3 to 5, techniques are disclosed whereby a program is executed in advance and information for files accessed by the program is collected as a profile, and whereby files are prefetched based on the profile. Further, according to non-patent document 3 and 4, a technique is disclosed whereby the order in which a series of files are to be accessed by individual programs is generated based on a profile, and whereby, when a specific file is accessed during the execution of a program, the next file is prefetched. According to the technique in non-patent document 5, information for designating a cluster that highly probably will be accessed next, following a current cluster, is stored for each cluster on a hard disk. Then, when a specific cluster is read, a cluster it is highly probable will be accessed is prefetched.
In non-patent documents 6 and 7, a method is disclosed whereby data to be prefetched from an external storage device are designated by a program, to ensure that appropriate data are prefetched.
In non-patent document 8, a method is disclosed whereby a file access pattern is detected by analyzing a program during the compilation, and the computer is used to insert a prefetching process into execution code.
In non-patent documents 9 and 10, a method is disclosed whereby prefetching is performed by using a prefetching program from which an unnecessary process to I/O, for example, is removed. That is, prior to the execution of an original program, a prefetching program is executed to prefetch data and the original program is permitted to use the obtained data.
In non-patent documents 11 and 12, a technique is disclosed whereby the order in which access requests are issued to a hard disk is rearranged to reduce the seek time for a head.    [Non-Patent Document 1] R. J. Feiertang and E. I. Organisk, “The Multics Input/Output System”, in Proceedings of Third Symposium on Operating System Principles, pp. 35-41, 1971    [Non-Patent Document 2] M. K. McKusick, W. J. Joy, S. J. Leffler, and R. S. Fabry, “A Fast File System for Unix”, ACM Transactions on Computer Systems, 2(3), pp. 181-197, 1984    [Non-Patent Document 3] H. Lei and D. Duchamp, “An Analytical Approach to File Prefetching”, USENIX 1997, 1997    [Non-Patent Document 4] J. Griffioen and R. Appleton, “Reducing File System Latency using a Predictive Approach”, in Proceedings of the USENIX Summer Technical Conference, pp. 197-207, 1994    [Non-Patent Document 5] K. S. Grimsrud, J. K. Archibald, and B. E. Nelson, “Multiple Prefetch Adaptive Disk Caching”, IEEE Transaction on Knowledge and Data Engineering, Vol. 5, No. 1, pp. 88-103, 1993    [Non-Patent Document 6] Jeffrey Richter, “Advanced Windows—The Developer's Guide to the Win32(r) API for Windows NT(tm) 3.5 and Windows 95”, Microsoft Press, 1995    [Non-Patent Document 7] R. H. Patterson, et. al., “Informed Prefetching and Caching”, in Proceedings of Fifteenth Symposium on Operating System Principles, pp. 79-95, 1995    [Non-Patent Document 8] T. C. Mowry, A. K. Demke, and O. Krieger, “Automatic Compiler-Inserted I/O Prefetching for Out-of-Core Application”, in Proceedings of the 2nd USENIX Symposium on Operating Systems Design and Implementation, 1996    [Non-Patent Document 9] C. K. Yang, T. Mitra, and T. C. Chiueh, “A Decoupled Architecture for Application-Specific File Prefetching”, USENIX 2002, 2002    [Non-Patent Document 10] K. Fraser and F. Chang, “Operating System I/O Speculation:
How two invocations are faster than one”, USENIX 2003, 2003    [Non-Patent Document 11] C. C. Gotlieb and G. H. MacEwen, “Performance of Movable-Head Disk Storage Devices”, Journal of ACM, Vol. 20, No. 4, pp. 604-623, 1973    [Non-Patent Document 12] R. Geist and S. Daniel, “A Continuum of Disk Scheduling Algorithms, ACM Transactions on Computer Systems”, Vol. 5, No. 1, pp. 77-92, 1987